List of knapsack problems について

Words near each other

Dictionary Lists

mini英和辞書

mini和英辞書

翻訳と辞書　辞書検索 [ 開発暫定版 ]

スポンサードリンク

List of knapsack problems ：ウィキペディア英語版

List of knapsack problems
The knapsack problem is one of the most studied problems in combinatorial optimization, with many real-life applications. For this reason, many special cases and generalizations have been examined.
Common to all versions are a set of ''n'' items, with each item

1 \leq j \leq n

having an associated profit ''p_j'' ,weight ''w_j''. The binary decision variable ''x_j'' is used to select the item. The objective is to pick some of the items, with maximal total profit, while obeying that the maximum total weight of the chosen items must not exceed ''W''. Generally, these coefficients are scaled to become integers, and they are almost always assumed to be positive.
The knapsack problem in its most basic form:
^n w_j x_j \leq W,
|
|-
|
|

x_j \in \

\forall j \in \

|}
==Direct generalizations==
One common variant is that each item can be chosen multiple times. The bounded knapsack problem specifies, for each item ''j'', an upper bound ''u_j'' (which may be a positive integer, or infinity) on the number of times item ''j'' can be selected:
^n w_j x_j \leq W,
|
|-
|
|

u_j \geq x_j \geq 0, x_j

integral for all ''j''
|}
The unbounded knapsack problem (sometimes called the integer knapsack problem) does not put any upper bounds on the number of times an item may be selected:
^n w_j x_j \leq W,
|
|-
|
|

x_j \geq 0, x_j

integral for all ''j''
|}
The unbounded variant was shown to be NP-complete in 1975 by Lueker. Both the bounded and unbounded variants admit an FPTAS (essentially the same as the one used in the 0-1 knapsack problem).
If the items are subdivided into ''k'' classes denoted

N_i

, and exactly one item must be taken from each class, we get the multiple-choice knapsack problem:
p_ x_
|
|-
|subject to
|

\sum_^k\sum_ w_ x_ \leq W,

|
|-
|
|

\sum_x_ = 1,

|for all

1 \leq i \leq k

|-
|
|

x_ \in \

|for all

1 \leq i \leq k

and all

j \in N_i

|}
If for each item the profits and weights are identical, we get the subset sum problem (often the corresponding decision problem is given instead):
^n p_j x_j \leq W,
|
|-
|
|

x_j \in \

|
|}
If we have ''n'' items and ''m'' knapsacks with capacities

W_i

, we get the multiple knapsack problem:
^n p_j x_
|
|-
|subject to
|

\sum_^n w_j x_ \leq W_i,

|for all

1 \leq i \leq m

|-
|
|

\sum_^m x_ \leq 1,

|for all

1 \leq j \leq n

|-
|
|

x_ \in \

|for all

1 \leq j \leq n

and all

1 \leq i \leq m

|}
As a special case of the multiple knapsack problem, when the profits are equal to weights and all bins have the same capacity, we can have multiple subset sum problem.
Quadratic knapsack problem:
^\sum_^n p_ x_i x_j
|
|-
|subject to
|

\sum_^n w_j x_j \leq W,

|
|-
|
|

x_j \in \

|for all

1 \leq j \leq n

|
|}
Set-Union Knapsack Problem:
SUKP is defined by Kellerer et al (on page 423) as follows:

Given a set of $n$ items $N = \$ and a set of $m$ so-called elements $P = \$ , each item $j$ corresponds to a subset $P_j$ of the element set $P$ . The items $j$ have non-negative profits $p_j$ , $j = 1, \ldots, n$ , and the elements $i$ have non-negative weights $w_i$ , $i = 1, \ldots, m$ . The total weight of a set of items is given by the total weight of the elements of the union of the corresponding element sets. The objective is to find a subset of the items with total weight not exceeding the knapsack capacity and maximal profit.

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「List of knapsack problems」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース